package com.dh.leetcode.k1;

import org.junit.Assert;
import org.junit.Test;

/**
 * @ClassName: _1356_Sort_integers_by_the_number_of_1_bits
 * @Description:
 * 二进制1个数排序
 * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
 * <p>
 * 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
 * <p>
 * 请你返回排序后的数组。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [0,1,2,3,4,5,6,7,8]
 * 输出：[0,1,2,4,8,3,5,6,7]
 * 解释：[0] 是唯一一个有 0 个 1 的数。
 * [1,2,4,8] 都有 1 个 1 。
 * [3,5,6] 有 2 个 1 。
 * [7] 有 3 个 1 。
 * 按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: shouzimu
 * @Date: 2020/11/13 17:22
 */
public class _1356_Sort_integers_by_the_number_of_1_bits {

    public int[] sortByBits(int[] arr) {
        if (null == arr) {
            return arr;
        }
        //use quick sort
        sort(arr, 0, arr.length - 1);
        return arr;
    }

    public void sort(int[] arr, int p, int r) {
        if (p < r) {
            int k = partition(arr, p, r);
            sort(arr, p, k - 1);
            sort(arr, k + 1, r);
        }
    }

    public int partition(int[] arr, int p, int r) {
        int x = arr[r];
        int k = p;
        for (; p < r; p++) {
            if (small(arr[p], x)) {
                swap(arr, k, p);
                k++;
            }
        }
        swap(arr, k, r);
        return k;
    }

    public boolean small(int x, int y) {
        int xb = hammingWeight(x);
        int yb = hammingWeight(y);
        return (xb == yb) ? x < y : xb < yb;
    }

    public int hammingWeight(int n) {
        int i = 0;
        while (n != 0) {
            n = n & (n - 1);
            i++;
        }
        return i;
    }

    private void swap(int[] a, int i, int j) {
        int swap = a[j];
        a[j] = a[i];
        a[i] = swap;
    }

    @Test
    public void sortByBitsTest() {
        int[] a = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8};
        int[] expect = new int[]{0, 1, 2, 4, 8, 3, 5, 6, 7};
        a = sortByBits(a);
        Assert.assertArrayEquals(a, expect);
    }

}